// 分割回文串

package Leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class solution_131 {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrace(result, 0, new ArrayList<String>(), s);
        return result;
    }

    public void backtrace(List<List<String>> result, int cur, List<String> combination, String s) {
        // 如果遍历完所有的字符
        if (cur == s.length()) {
            // 如果组合中有不回文则去除
            for (String string : combination) {
                StringBuilder sb = new StringBuilder(string);
                String string1 = sb.reverse().toString();
                if (!string.equals(string1))
                    return;
            }
            result.add(new ArrayList<>(combination));
            return;
        }

        if (combination.size() == 0) {
            combination.add(String.valueOf(s.charAt(cur)));
            backtrace(result, cur + 1, combination, s);
            combination.remove(combination.size() - 1);
        } else {
            // 可以添加在最后一个字符串后面
            String string = combination.get(combination.size() - 1);
            string = string + s.charAt(cur);
            combination.set(combination.size() - 1, string);
            backtrace(result, cur + 1, combination, s);
            string = string.substring(0, string.length() - 1);
            combination.set(combination.size() - 1, string);
            // 也可以独立成为一个新的字符串
            combination.add(String.valueOf(s.charAt(cur)));
            backtrace(result, cur + 1, combination, s);
            combination.remove(combination.size() - 1);
        }
    }

    public static void main(String[] args) {
        solution_131 s131 = new solution_131();
        String s = "aab";
        s131.partition(s);
    }
}

public class Solution131 {
    boolean[][] huiwen;
    List<List<String>> result = new ArrayList<>();
    List<String> combination = new ArrayList<>();
    int length;

    public List<List<String>> partition(String s) {
        this.length = s.length();
        huiwen = new boolean[length][length];
        for (int i = 0; i < length; i++)
            Arrays.fill(huiwen[i], true);

        for (int i = 1; i <= s.length(); i++)
            for (int j = 0; j + i < s.length(); j++)
                huiwen[j][i + j] = (s.charAt(j) == s.charAt(i + j)) && huiwen[j + 1][i + j - 1];

        backtrace(s, 0);

        return this.result;
    }

    public void backtrace(String s, int cur) {
        if (cur == length)
            result.add(new ArrayList<>(combination));

        for (int i = cur; i < length; i++) {
            if (huiwen[cur][i]) {
                combination.add(s.substring(cur, i + 1));
                backtrace(s, i + 1);
                combination.remove(combination.size() - 1);
            }
        }
    }
}